﻿// 贪心 · 例4-排座椅.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
链接：https://ac.nowcoder.com/acm/contest/20960/1026
来源：牛客网

同学们在教室中坐成了n 行m 列，坐在第i 行第j 列的同学的位置是(i,j) 。同时，为了方便同学们进出，在教室中设置了k 条横向的通道，l 条纵向的通道。
然而，上课的时候总有一些同学和**前后左右**的人交头接耳，这是令班主任十分头疼的一件事情。她统计了班级中经常交头接耳的d 对同学，并记录了他们的位置。
现在，她想要重新调整横纵通道的位置，使得交头接耳的同学尽可能都被通道隔开。请你帮助编写一个程序，给出最好的通道划分方案。
在该方案下，没有被通道隔开的交头接耳的学生对数最少。
输入描述:
第一行输入五个整数n,m,k,l,d
(2≦n,m≦103; 0<k<n; 0<l<m; 0<d≦2×min{n×m,2×103 }) 代表教室的行数、列数、横向通道数、纵向通道数、交头接耳的学生对数。
此后d 行，第i 行输入四个整数𝑥𝑖,𝑦𝑖,𝑝𝑖,𝑞𝑖xi
​代表坐在位置(𝑥𝑖,𝑦𝑖) 与(𝑝𝑖,𝑞𝑖) 的两个同学会交头接耳。保证这两个位置存在、不同，且前后相邻或者左右相邻。

保证最优方案存在，且唯一存在。
输出描述:
第一行输出k 个整数
𝑎1,𝑎2,~~,𝑎𝑘(1≦𝑎𝑖<𝑎𝑖+1≦𝑛−1) ，第i 个整数ai 代表第ai 行和ai+1 行之间有一条横向通道。
第二行包含l 个整数
𝑏1,𝑏2,~~,𝑏𝑙(1≦𝑏𝑖<𝑏𝑖+1≦𝑚−1)第i 个整数bi 代表第bi 列和bi+1 列之间有一条纵向通道。
示例1
输入
复制
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
输出
复制
2
2 4
说明
该样例如下图所示，蓝底斜线方格为第一对交头接耳的同学，绿底带叉方格为第二对交头接耳的同学，粉底带星方格为第三对交头接耳的同学。
粗线代表通道。该划分方案为唯一最优方案。

链接：https://ac.nowcoder.com/acm/contest/20960/1026
来源：牛客网

示例2
输入
复制
2 2 1 1 4
1 1 1 2
1 1 2 1
2 1 2 2
1 2 2 2
输出
复制
1
1
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

